package com.example.algorithm;

/**
 * 98. 验证二叉搜索树
 *
 * @author huahua
 * @DATE 2025/4/5
 **/
public class validBST {
    public static void main(String[] args) {

    }

    // 方法1
    // 前一个节点
    TreeNode pre = new TreeNode();
    public boolean isValidBST1(TreeNode root) {
        // 对数进行中序遍历，如果结果是递增，则代表是有效二叉搜索树；否则，不是
        // 不用比较全部节点，只需要比较当前节点和前一个节点即可。
        // 如果当前节点值小于前一个节点，则不是有效二叉搜索树；否则，是。
        // 递归判断左子树，然后判断当前节点和上一个节点值，最后递归判断右子树。
        if(root == null){
            return true;
        }

        if(!isValidBST1(root.left)){
            return false;
        }

        // 如果当前节点值小于前一个节点，则不是有效二叉搜索树；
        if(pre != null && pre.val >= root.val){
              return false;
        }

        // 更新前一个节点为当前节点
        pre = root;

        return isValidBST1(root.right);
    }


    // 方法2
    public boolean isValidBST2(TreeNode root) {
        return checkValidBST(root, null, null);
    }

    /*
     * 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val
    */
    boolean checkValidBST(TreeNode root, TreeNode min, TreeNode max) {
        if(root == null){
            return true;
        }
        // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
        if( min != null && root.val <= min.val){
            return false;
        }
        if(max!= null && root.val >= max.val){
            return false;
        }

        // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
        return checkValidBST(root.left,min,root) && checkValidBST(root.right,root,max);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
